package tests;

import java.util.ArrayList;

import junit.framework.TestCase;
import lib.*;
import trees.*;


public class QuadTreeTest extends TestCase {


	/**
	 * Tests that the correct behavior is exhibited after the constructor
	 */
	public void testConstructor() {
		QuadTree<String> tree;
		
		tree = new QuadTree<String>();
		assertEquals("initial size incorrect", 0, tree.size());
		assertEquals("initial depth incorrect", 0, tree.depth());
	}

	public void testSimpleInsert() {
		QuadTree<String> tree = new QuadTree<String>();
		tree.insert(new CartesianPoint(3,2), "A");
		assertEquals("one-insert size incorrect", 1, tree.size());
		assertEquals("one-insert depth incorrect", 1, tree.depth());
		assertEquals("inserted element not found", "A", tree.getClosest(new CartesianPoint(3,2))) ;
	}

	/**
	 * Inserts small sets of elements and tests that the correct  closest 
	 * proximity is returned
	 */
	public void testSimpleInsertOrder() {
		QuadTree<String> tree;
		// simple 1D cases
		tree = new QuadTree<String>();
		tree.insert(new CartesianPoint(0,-12), "A");
		tree.insert(new CartesianPoint(0,13), "B");
		tree.insert(new CartesianPoint(0,14.5), "C");
		assertEquals("Incorrect closest point", "A", tree.getClosest(new CartesianPoint(0,0)));
		assertEquals("Incorrect closest point", "B", tree.getClosest(new CartesianPoint(0,0.6)));
		assertEquals("Incorrect closest point", "C", tree.getClosest(new CartesianPoint(0,13.9)));

		// simple 2D cases
		tree = new QuadTree<String>();
		tree.insert(new CartesianPoint(10,5), "A");
		tree.insert(new CartesianPoint(12.5,2.5), "B");
		tree.insert(new CartesianPoint(5,5), "C");
		tree.insert(new CartesianPoint(7.5,10), "D");
		assertEquals("Incorrect closest point", "C", tree.getClosest(new CartesianPoint(0.00,0.00)));
		assertEquals("Incorrect closest point", "B", tree.getClosest(new CartesianPoint(10.00,0.00)));
		assertEquals("Incorrect closest point", "A", tree.getClosest(new CartesianPoint(10.00,2.501)));
		assertEquals("Incorrect closest point", "B", tree.getClosest(new CartesianPoint(10.00,2.499)));
		assertEquals("Incorrect closest point", "C", tree.getClosest(new CartesianPoint(7.49,5.00)));
		assertEquals("Incorrect closest point", "A", tree.getClosest(new CartesianPoint(7.51,5.00)));
		assertEquals("Incorrect closest point", "C", tree.getClosest(new CartesianPoint(7.49,2.00)));
		assertEquals("Incorrect closest point", "A", tree.getClosest(new CartesianPoint(7.51,2.00)));
	}

	
	public void testIterator() {
		QuadTree<String> tree;
		int iteratorSize;
		int testSize = 300000;
		tree = new QuadTree<String>();
		for (int i = 0;i < testSize;i ++)
			tree.insert(new CartesianPoint(Math.random() * 1000,Math.random() * 1000), "" + i);
		Iterable<String> iterator = tree.iterator();
		iteratorSize = 0;
		for (String s : iterator) {
			iteratorSize ++;
//			System.out.println(s);
		}
		assertEquals("Iterator missing elements", testSize, iteratorSize);
	}
	
	public void testGetWithinBounds() {
		QuadTree<String> tree;
		ArrayList<String> results;
		CartesianPoint lowLeft, upRight;
		tree = new QuadTree<String>();
		int low = 3;
		int high = 9;
		lowLeft = new CartesianPoint(low,low);
		upRight = new CartesianPoint(high,high);
		for (int x = 0; x < 100; x ++)
			for (int y = 0; y < 100; y ++)
				tree.insert(new CartesianPoint(x,y), "" + (x+(y*100)));
		results = tree.getWithinBounds(new RectangleArea(lowLeft, upRight));

		for (int x = 0; x < 100; x ++)
			for (int y = 0; y < 100; y ++)
				if (low <= x && x <= high && low <= y && y <= high)
					assertTrue("Boundary element not included", results.contains("" + (x+(y*100))));
				else
					assertFalse("Boundary element invalid inclusion", results.contains("" + (x+(y*100))));
	}
	
	public void testGetClosestPair() {
		QuadTree<String> tree;
		tree = new QuadTree<String>();
		tree.insert(new CartesianPoint(-12.00, 00.00), "A");
		tree.insert(new CartesianPoint( 13.00, 00.00), "B");
		tree.insert(new CartesianPoint( 14.50, 20.00), "C");
//		for (int i = 10;i < 90;i ++)
//			tree.insert(new CartesianPoint(Math.random() * 100,Math.random() * 100), "" + i);
//		assertEquals("Incorrect closest point", , tree.getClosestPair());
		System.out.println(tree.getClosestPair());
		System.out.println(tree.getClosestPair().getLength());

		for (int i = 0; i < 100; i ++) {
			for (int j = 0; j < 100; j ++)
				System.out.print(tree.getClosest(new CartesianPoint(j,i)));
			System.out.println();
		}

	}
	
//	public void testPrettyImage() {
//		QuadTree<String> tree = new QuadTree<String>();
//		for (int i = 10;i < 30;i ++)
//			tree.insert(new CartesianPoint(Math.random() * 100,Math.random() * 100), "" + i);
//		for (int i = 0; i < 100; i ++) {
//			for (int j = 0; j < 100; j ++)
//				System.out.print(tree.getClosest(new CartesianPoint(i,j)));
//			System.out.println();
//		}
//	}
}
